import java.awt.*;
import java.util.Arrays;

public class BackPack01 {
    public static void main(String[] args) {
        //01背包问题
        int[] weight={1,4,3};//物品的重量
        int[] value={1500,3000,2000};//物品的价值
        int capacity=4;//背包的容量
        int[][] v=new int[value.length+1][capacity+1];
        int[][] path=new int[value.length+1][capacity+1];//用于记录背包放过的商品

        //背包的容量为0时，价值为0，没有商品时，价值也为0
        for(int i=0;i<v.length;i++) {
            v[0][i] = 0;//将第0行初始化为0
            v[i][0] = 0;
        }
        //实现01背包问题--背包的容量是capacity=4
        for(int i=1;i<v.length;i++){//i-->代表商品
          for(int j=1;j<v[i].length;j++){//j-->代表背包的容量

              //如果物品的容量>背包的容量,继承
              if(weight[i-1]>j){
                  v[i][j]=v[i-1][j];
              }else{
                  //如果物品的容量<=背包的容量时，要比较价值的最优解
                 // v[i][j]=Math.max(v[i-1][j],value[i-1]+v[i-1][j-weight[i-1]]);
                  if(v[i-1][j]<value[i-1]+v[i-1][j-weight[i-1]]){
                      //说明最大价值是当前值
                      v[i][j]=value[i-1]+v[i-1][j-weight[i-1]];
                      //最后一次放入背包的商品，即最终结果会出现在这里。
                      path[i][j]=1;//i->表示当前的商品，j表示重量
                  }else{
                      //说明最大价值为继承
                      v[i][j]=v[i-1][j];
                  }
              }

          }

        }
        //输出最大价值时背包装入的商品

        for(int[] i:v){
            System.out.println(Arrays.toString(i));
        }
        System.out.println("----------------");


        //因为我们要统计的是最后一次放到背包的商品，但是我们在path中记录的是整个过程商品放入背包的
        //路径，因此我们可以逆向找，逆向找到的第一个商品若它的重量等于了背包的重量，那么此时背包中
        //就放了这一个商品，若是逆向找到的这个商品的重量是小于背包的容量的，那么就说明背包里还放了
        //其他的商品。

        int row=path.length-1;//记录行的最大下标
        int column=path[0].length-1;//记录列的最大下标
        while(row>0 && column>0){
            //path中放的商品的价值都不是继承上个商品的价值的，而是当前商品的价值或当前商品和其他商品的总价值
            //是用1表示非继承
            if(path[row][column]==1){
                System.out.printf("将第%d个商品放到背包中%n",row);
                column-=weight[row-1];
            }
            row--;
        }

    }

}
